/*
 * Towers of Hanoi.
 */

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <math.h>

unsigned long int total_moves; // Track the number of moves

typedef struct {
	int *disks; // Disk size range: 1..ndisks. 0 indicates no disk.
	int numdisks; // Number of disks on this pillar. Range: 1..ndisks.
	int pillar_no;
	int *totaldisks; // Points to the total number of disks. Added this so
	   // that I don't need to pass around ndisks everywhere as an argument
} Pillar;

// Initializes pillars
void Pillar_init(Pillar P[], int *ndisks) {
	int i;

	for ( i = 0; i < 3; i++ )
		P[i].disks = malloc(*ndisks * sizeof(int));

	P[0].numdisks = *ndisks;
	P[1].numdisks = 0;
	P[2].numdisks = 0;

	// Add all the disks on the first pillar, leaving the other 2 empty
	for ( i = 0; i < *ndisks; i++ ) {
		P[0].disks[i] = *ndisks - i;
		P[1].disks[i] = 0;
		P[2].disks[i] = 0;
	}

	P[0].pillar_no = 0;
	P[1].pillar_no = 1;
	P[2].pillar_no = 2;

	P[0].totaldisks = ndisks;
	P[1].totaldisks = ndisks;
	P[2].totaldisks = ndisks;
}

void Pillar_display_all(Pillar P[]) {
	int i, j;

	for ( i = 0; i < 3; i++ ) {
		printf("Pillar %d: ", P[i].pillar_no);
		for ( j = 0; j < *(P[i].totaldisks); j++ ) {
			if ( P[i].disks[j] == 0 )
				printf("\t-");
			else
				printf("\t%d", P[i].disks[j]);
		}
		printf("\n");
	}
	printf("---\n");
}

// Moves the topmost disk of A on top of pillar B
void disk_move(Pillar P[], int a, int b) {
	P[b].disks[P[b].numdisks] = P[a].disks[P[a].numdisks-1];
	P[a].disks[P[a].numdisks-1] = 0;
	P[b].numdisks++;
	P[a].numdisks--;
	total_moves++;
	Pillar_display_all(P);
}

void exchange(Pillar P[], int a, int b) {
	if ( P[a].numdisks == 0 ) {
		disk_move(P, b, a);
		return;
	}
	else if ( P[b].numdisks == 0 ) {
		disk_move(P, a, b);
		return;
	}

	if ( P[a].disks[P[a].numdisks-1] > P[b].disks[P[b].numdisks-1] )
		disk_move(P, b, a);
	else
		disk_move(P, a, b);
}

void start(Pillar P[], int moves[3][2], int move) {
	exchange(P, moves[move][0], moves[move][1]);
	while ( P[2].numdisks < *(P[2].totaldisks) )
		start(P, moves, (move == 2) ? 0 : move+1);
}

int main(int argc, char *argv[])
{
	Pillar p[3]; // 3 pillars. Don't change the number.

	if ( argc < 2 ) {
		fprintf(stderr, "Please specify the number of disks\n");
		return -1;
	}
	int ndisks = atoi(argv[1]);
	if ( ndisks > 15 && ndisks <= 32 ) {
		printf("There would be %.0f moves. We won't do that much recursion as"\
			   " the stack could exceed its limits\n", pow(2, ndisks) - 1);
		return 0;
	} else if ( ndisks > 32 ) {
		fprintf(stderr, "Sorry, can't handle that many disks\n");
		return 1;
	}
	Pillar_init(p, &ndisks);

	total_moves = 0;

	int moves_odd[3][2] = {{0, 2}, {0, 1}, {1, 2}};
	int moves_even[3][2] = {{0, 1}, {0, 2}, {1, 2}};

	if ( p[0].numdisks % 2 == 0 )
		start(p, moves_even, 0);
	else
		start(p, moves_odd, 0);

	printf("STOP. Total moves: %ld\n", total_moves);

	return 0;
}
